package Tree;

import Queue.LinkedQueue;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created by Administrator on 2017/10/27/027.
 */
public class NewTree {
    public static ArrayList<String> DLR = new ArrayList<String>();
    public static ArrayList<String> LDR = new ArrayList<String>();
    static node root = new node();

    public static class node {
        node right;
        node left;
        String data;

        node(String ndata) {
            data = ndata;
            right = null;
            left = null;
        }

        public node() {
            right = null;
            left = null;
        }
    }

    public static void BuildTree(node element, ArrayList<String> a, ArrayList<String> b) {
        element.data = a.get(0);//前序第一个元素必为根节点
        if (a.size() <= 1) {
            return;
        }
        element.left = new node();
        element.right = new node();
        //两个序列的拆分索引
        int index1 = 0;
        int index2 = 0;
        /*拆分序列*/
        ArrayList<String> aleft = new ArrayList<String>();
        ArrayList<String> aright = new ArrayList<String>();
        ArrayList<String> bleft = new ArrayList<String>();
        ArrayList<String> bright = new ArrayList<String>();
        //拆分中序
        for (int i = 0; i < b.size(); i++) {
            if (b.get(i) == element.data) {
                b.remove(i);
                i--;
                index1 = i;
                break;
            }
        }

        //生成新的中序（左）
        for (int i = 0; i <= index1; i++) {

            bleft.add(b.get(i));
        }
        //生成新的中序（右）
        for (int j = index1 + 1; j < b.size(); j++) {
            bright.add(b.get(j));
        }
        //拆分前序，确定分离的元素索引
        if (bright.isEmpty()) {
            //中序右为空，前序全为左子树
            for (int i = 1; i < a.size(); i++) {
                aleft.add(a.get(i));
            }
            element.right = null;
            BuildTree(element.left, aleft, bleft);
        } else {
            if (bleft.isEmpty()) {
                //中序左为空，前序全为右子树
                for (int i = 1; i < a.size(); i++) {
                    aright.add(a.get(i));
                }
                element.left = null;
                BuildTree(element.right, aright, bright);
            } else {
                //均不为空，分别生成
                outer:
                for (int i = 0; i < a.size(); i++) {

                    for (int j = 0; j < bright.size(); j++) {

                        if (a.get(j) == bright.get(j)) {

                            index2 = j;
                            break outer;
                        }
                    }
                }


                for (int i = 1; i < index2; i++) {
                    aleft.add(a.get(i));
                }
                for (int j = index2; j < a.size(); j++) {
                    aright.add(a.get(j));
                }
                BuildTree(element.left, aleft, bleft);
                BuildTree(element.right, aright, bright);
            }
        }
    }

    public static void preorder(node x) {
        System.out.print(x.data + ",");

        if (x.left != null) {
            preorder(x.left);
        }

        if (x.right != null) {
            preorder(x.right);
        }
    }

    public static void inorder(node x) {

        if (x.left != null) {
            inorder(x.left);
        }

        System.out.print(x.data + ",");

        if (x.right != null) {
            inorder(x.right);
        }

    }

    public static void postorder(node x) {
        if (x.left != null) {
            postorder(x.left);
        }
        if (x.right != null) {
            postorder(x.right);
        }
        System.out.print(x.data + ",");
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String bp = scan.nextLine();
        String[] DLR = bp.split(" ");
        //String[]DLR = new
        for (int i = 0; i < DLR.length; i++) {
            String qxdata = DLR[i];
            NewTree.DLR.add(String.valueOf(qxdata));
        }
        bp = scan.nextLine();
        String[] LDR = bp.split(" ");
        for (int i = 0; i < LDR.length; i++) {
            String zxdata = LDR[i];
            NewTree.LDR.add(String.valueOf(zxdata));
        }
    }
}
